package com.yangzhe.algorithm.c042;

// 草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃
// 每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64....
// 谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢
public class Code02_EatGrass {
    /**
     * "A"  "B"
     * <p>
     * 暴力递归思路：
     * 1. A牛先吃 0次幂 1次幂...直到剩下的草不够，分别调用递归子过程得知谁赢
     * 2. 如果子过程有A赢则算A赢，如果没有则算B赢
     * <p>
     * 谁赢 String who = whoWin(restGrass, nextBull)
     *
     * @param n
     * @return
     */
    public static String win1(int n) {
        return whoWin(n, "A");
    }

    public static String whoWin(int restGrass, String nextBull) {
        String whoWin;
        String otherBull = nextBull.equals("A") ? "B" : "A";

        // base case: 如果剩余的草不足4个，则无法继续递归
        //  	A	B
        // 0		√
        // 1	√
        // 2		√
        // 3	√
        // 4	√
        if (restGrass <= 4) {
            if (restGrass == 0 || restGrass == 2) {
                return otherBull;
            } else {
                return nextBull;
            }
        }

        for (int exponent = 0; restGrass - (int) Math.pow(4, exponent) >= 0; exponent++) {
            whoWin = whoWin(restGrass - (int) Math.pow(4, exponent), otherBull);
            if (whoWin.equals(nextBull)) {
                return whoWin;
            }
        }

        return otherBull;

    }

    /**
     * 打表：
     * 规律是 B A B A A
     *
     * @param n
     * @return
     */
    public static String win2(int n) {
        int mod = n % 5;
        if (mod == 0 || mod == 2) {
            return "B";
        } else {
            return "A";
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 50; i++) {
            System.out.println(i + " : " + win1(i));
            System.out.println(i + " : " + win2(i));
        }
    }

}
